package algorithm.middle;

import pojo.TreeNode;

/**
 * 给定一个有 N 个结点的二叉树的根结点 root，树中的每个结点上都对应有 node.val 枚硬币，并且总共有 N 枚硬币。
 *
 * 在一次移动中，我们可以选择两个相邻的结点，然后将一枚硬币从其中一个结点移动到另一个结点。(移动可以是从父结点到子结点，或者从子结点移动到父结点。)。
 *
 * 返回使每个结点上只有一枚硬币所需的移动次数。
 */
public class DistributeCoins979 {

    /**
     * 贡献法
     * 节点上面路经通过的硬币数量 子树coin总量-子树node总量
     * coins = coins_l + coins_r + node.val
     * nodes = nodes_l + nodes_r + 1
     * 统计 SUM（｜coins - nodes｜）
     */
    public int distributeCoins(TreeNode root) {
        int[] dfs = dfs(root);
        return dfs[2];
    }

    /**
     * 深度便利
     * int[0] 节点数量
     * int[1] 硬币数量
     * int[2] 绝对值结果
     */
    private int[] dfs(TreeNode node) {
        if (node == null) {
            return new int[3];
        }
        int[] left = dfs(node.left);
        int[] right = dfs(node.right);
        int coins = left[1] + right[1] + node.val;
        int nodes = left[0] + right[0] + 1;
        int res = Math.abs(coins - nodes) + left[2] + right[2];
        return new int[]{nodes, coins,res};
    }

}
